package 算法.leetcode.offer;

/**
 * @author lchenglong
 * @date 2022/4/21
 */
public class Offer14_II {

    public static void main(String[] args) {
        Offer14_II instance = new Offer14_II();
        int ans = instance.cuttingRope(1000);
        System.out.println(ans);
    }

    public int cuttingRope(int n) {
        if (n <= 3) return n - 1;
        // 先分成三段
        int count = n / 3;
        // 看看余多少
        int rem = n % 3;
        int p = 1000000007;
        long ans = 1;
        for (int i = 1; i < count; i++) {
            //
            ans =( ans * 3) % p;
        }
        if (rem == 0) return (int) ((ans * 3) % p);
        if (rem == 1) return (int) ((ans * 4 )% p);
        return (int) ((ans * 6) % p);
    }
}
